Finite state machine (FSM) and combinational logic synthesis have been conventionally targeted to reducing the area and the critical path delay. Recently, testability has also been considered. However, power dissipation considerations have received little attention. The minimization of power in CMOS circuits is of extreme importance, especially for portable operations. As the number of devices on a chip increases, the heat dissipation requirements can become prohibitively large. Power dissipation in CMOS circuits has traditionally been minimized by scaling down the supply voltage. However, when the supply voltage is scaled down, the circuit performance becomes slower. The slower performance can be compensated for by using scaled down device features, but several other effects such as dominant interconnect capacitance becomes very important. Accordingly, there is a need for FSM synthesis that also minimizes power dissipation.